package leetcode;

import java.util.Arrays;

/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q2563.java
 * @Author : WangRuoyu
 * @Date 2023/2/22 11:23
 */

// TODO
public class Q2563 {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long res = 0;

        Arrays.sort(nums);

        int p = 0;
        int q = nums.length - 1;
        int tmpp;
        int tmpq;

        while (p < q) {
            if (nums[p] > (upper - nums[q])) {
                q--;
            } else if (nums[p] < (lower - nums[q])) {
                p++;
            } else {
                res++;
                tmpq = q;
                tmpq--;
                while ((p < tmpq) && (nums[p] >= (lower - nums[tmpq]))) {
                    res++;
                    tmpq--;
                }
                tmpp = p;
                tmpp++;
                while ((tmpp < q) && (nums[tmpp] <= (upper - nums[q]))) {
                    res++;
                    tmpp++;
                }
                q--;
                p++;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Q2563 sl = new Q2563();
        int[] nums = {0, 1, 7, 4, 4, 5};
        int lower = 3;
        int upper = 6;
        System.out.println(sl.countFairPairs(nums, lower, upper));
    }
}